package leetcode;
/*
 * 这道题 也让我明白 dp 能解决 什么 样的  问题 不能 解决 什么  样的 问题
 * 以及  暴力 递归  （回溯 ） 能解决 什么样的 问题    暴力递归 坑定能解决 dp 解决 不了的  问题
 */
import java.util.ArrayList;
import java.util.List;
public class leetcode1447最简分数 {
	
	public  static List<String> solution2(int n){
		List<String> ans =new ArrayList<String>(); 
		for(int i=1 ;i< n;i++) {
			for(int j=i+1;j<=n ;j++) {
				if(gcd(i,j)==1) {
					ans.add(i+"/"+j);
				}
			}
		}
		return  ans;
	}
	//  判断是 不是  最大公因数 如果返回 一  1 最大公因数为 1  
	public static int  gcd(int a,int b) {

		return b !=0 ? gcd(b,a%b) : a;
		
		
		//		if(b==0) {
//			return false;
//		}
//		b=a%b;
//		return gcd(b,a);
//		return false;
//		
//		 if(a%b == 0) {
//			return true;
//		 }
//		  b= a%b;
//	     gcd(b,a);
//		return false;
	}
	
	
	
	
	
	
	
	
	
	
	
	//      简直   麻了  直接  暴力 如果 暴力 解决 不掉 再去 优化 呗  先把 题 ac 再说呗
	public static void main(String []args) {
		List<String> arr =new ArrayList<>();
//		arr.add("a");
//		arr.add("a");
//		arr.add("a");
//		arr.toString();
		
//		process(4,1,arr);
		solution(6);
		System.out.println();
//		System.out.println(arr);
		
	}
	public static  void process(int n,int index,List<String> ans) {
		if(index==1 || n % index !=0) {
			ans.add(index+"/"+n);
		}
		for(int i=index;i < n;i++) {
				process(n,i+1,ans);
		}
		
	}
	public static void solution(int n) {
		List<String> arr =new ArrayList<>();
		for(int i=n;i>1;i--) {
			process1(i,1,arr);
		}
		System.out.println(arr);
	}
	public static void process1(int n,int index,List<String> ans) {
		if(index == n)
			return ;
		if(index==1 || gcd(index,n)==1) {
			ans.add(index+"/"+n);
		}
		process1(n,index+1,ans);
	}
}
